package ljl.codetop300;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
 * 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代
 *
 * temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 *
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 示例 3:
 *
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 *
 * 做好几遍了，单调栈
 */
public class _739_dailyTemperatures {

  /**
   * Can I?
   * 不会做，操他妈
   */
  static class m {
    public int[] dailyTemperatures(int[] temperatures) {
      int length = temperatures.length;
      // 这个栈用来保存还没确定结果的索引
      int[] ans = new int[length];
      Deque<Integer> stack = new LinkedList<>();
      for (int i = 0; i < length; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
          int prevIndex = stack.pop();
          ans[prevIndex] = i - prevIndex;
        }
        stack.push(i);
      }
      return ans;
    }
  }

  static class itry {
    public int[] dailyTemperatures(int[] temperatures) {
      int n = temperatures.length;
      int[] res = new int[n];
      LinkedList<Integer> q = new LinkedList<>();
      for (int i = 0; i < n; i++) {
        while (!q.isEmpty() && temperatures[i] > temperatures[q.peek()]) {
          int j = q.pop();
          res[j] = i - j;
        }
        q.push(i);
      }
      return res;
    }
  }
}
